package BinaryTree;

import java.util.HashMap;
import java.util.Map;
/*
* 路径总和3
* hashmap加前缀和
*
* 将题解答案的局部变量res改成了全局变量res
* */
public class PathSum437 {
    int res=0;
    public int pathSum(TreeNode root, int sum) {
        Map<Integer, Integer> map = new HashMap<>();
        map.put(0, 1);
        dfs(root,sum,map,0);
        return res;
    }

    private void dfs(TreeNode root, int sum, Map<Integer, Integer> map, int curr) {
        if(root==null)return;
        curr+=root.val;
        res+= map.getOrDefault(curr-sum,0);
        map.put(curr, map.getOrDefault(curr, 0) + 1);
        dfs(root.left,sum,map,curr);
        dfs(root.right,sum,map,curr);
        map.put(curr,map.getOrDefault(curr,0)-1);
        return;
    }


}

